In communications systems, it is sometimes needed or desired to multicast the same data to multiple nodes, for certain application. When the channel is unreliable, it may not be possible to deliver the data to all receivers in a reliable way. Solving this problem is a challenge to protocol designers. Usually feedback messages from the receivers to the sender are used to enable the sender to determine which packets have been received correctly by the intended receivers and which ones have not. The packets that have not been received correctly must be resent. Multiple parallel unicast ARQ processes may be used to ensure reliable multicast. This is, however, an inefficient way of communication. It is typically considered more efficient to merge the parallel unicast processes into a single multicast ARQ process.
If there are K receivers, the term fully reliable multicast indicates that all packets should be received by all K receivers. The term k-reliable multicast indicates that each packet should be delivered to at least k of the K receivers.
Automatic repeat request (ARQ) is proposed to be used for the communication over the air interface in cellular wireless communication systems. ARQ could also be used in multihop systems. The data is, prior to the transmission, typically divided into smaller packets, protocol data units (PDU). A reliable transfer is enabled by encoding packets with an error detecting code, such that the receiver can detect erroneous or lost packets and thereby request a retransmission. The data sequence integrity is normally accomplished by sequential numbering of packets and applying certain transmission rules.
In the most simple form of ARQ, commonly referred to as Stop-and-Wait ARQ, the sender of data stores each sent data packet and waits for an acknowledgement from the receiver of a correctly received data packet, by the way of an acknowledgement message (ACK). When the ACK is received, the sender discards the stored packet and sends the next packet. The process is typically supplemented with timers and the use of negative acknowledgement messages (NACK). The sending entity uses a timer, which is started on the transmission of a data packet, and if no ACK (or NACK) has been received before the timer expires, the data packet is retransmitted. If the receiver detects errors in the packet, it can send a NACK to sender. Upon receiving the NACK, the sender retransmits the data packet without waiting for the timer to expire. If the ACK or NACK message is lost, the timer will eventually expire and the sender will retransmit the data packet.
Co-pending application PCT/SE 2005/001144 discloses an improved scheduling and coding method and arrangement exploiting the fact of information being received by other nodes in the system than the initially designated receiving node, that is suitable in communication systems utilizing automatic repeat request (ARQ) or multihop scheduling and forwarding, wherein the media is unreliable, is needed.
This co-pending application proposes a method and an arrangement for unicast facilitating the use of overheard, and previously discarded, information for improving the encoding and scheduling in a sending node. According to the method each receiving node selectively stores received information as a priori information and feeds back information about their respective stored a priori information to a sending node, for example, in the form of Acknowledgements messages. The sending node forms composite multicast data packets by jointly encoding and scheduling multiple data packets to multiple nodes, at least partly based on the feedback about the receiving nodes respective a priori information. The sending node transmits the composite multicast data packet to a plurality of receiving nodes. Upon receiving a composite multicast data packet the receiving nodes uses their stored a priori information in the process of extracting data for themselves from the composite multicast data packets. In addition, and in combination with the a priori information feedback, the sending node utilizes conventional feedback informing about received data packets.
The solution described in the co-pending application is applicable in multiple Unicast ARQ (e.g. in cellular and multihop systems) as well as in multihop systems where information overhearing may also stem from other senders than the sender node. The term multiple Unicast ARQ, in this context means that different data is targeted for each node.
The co-pending application does however not address multicast communication. A problem with traditional multicast ARQ is that the performance is poor when the number of nodes is large.
The following calculations are based on some assumptions: The nodes are assumed to have identical packet sizes, data rates and identical independent distributed (i.i.d.) reception probabilities. Further, non-sequence number limited ARQ, error free feedback, full buffers and a large number of packet analysis are assumed.
The throughput efficiency for fully reliable multicast can be derived and formulated through the recursive formula
                                                                        T                K                            =                                                N                  ′                                                                      M                    ′                                    +                                      M                    ″                                                                                                                          =                                                                    N                    ′                                    /                                      M                    ′                                                                    1                  +                                                            M                      ″                                        /                                          M                      ′                                                                                                                                              =                                                1                  -                                      q                    K                                                                    1                  +                                                            ∑                                              j                        =                        1                                                                    K                        -                        1                                                              ⁢                                                                  (                                                                                                            K                                                                                                                                          j                                                                                                      )                                            ⁢                                              p                        j                                            ⁢                                              q                                                  K                          -                          j                                                                    ⁢                                              1                                                  T                                                      K                            -                            j                                                                                                                                                                                                      (        1        )            where    T=throughput    N′ is the number o packets received by a node    M′ is the number of packets send in a first phase    M″ is the number of packets sent in a subsequent transmission    K is the number of nodes    q is the probability of failure    p is the probability of correct reception    j is the number of nodes that have received identical packets.
The motivation for (1) is that M′(1−qK) different packets are received by any node, when M′ packets are sent in a first phase. In subsequent transmissions, M″, it is then the task to deliver any packet in this set to all K nodes. We note that after the first transmission, a packet may have been received by one or more nodes. A set of such packets where each packet have been received by the same j nodes, are here said to be a set of packets at “level j”. There are K over j different such sets of each level, with M′pjqK−j packets in each such set. The denominator is the normalized number of transmissions needed to deliver each packet to at least k nodes. The normalization is with respect to the initial number of transmissions in the firsts phase, M′, hence the 1+sum throughput efficiency term in the denominator. In the sum of the denominator, we account for that each level j has a number of packets that takes on average 1/TK−j transmissions per packet.
While the throughput is derived under the assumption of identical packet sizes, identical data rates and i.i.d. reception probabilities, in practise, different packet sizes, different data rated and non-identical (non-i.i.d) reception probabilities apply.